package sword_offer;

/**
 * @author Synhard
 * @version 1.0
 * @Class sword_offer.Code12
 * @Description 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，
 * 它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。
 * 例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，
 * 因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-13 17:00
 */
public class Code12 {

    int counter = 0;

    public static void main(String[] args) {
        Code12 code12 = new Code12();
        System.out.println(code12.movingCount(3, 2, 17));
    }

    public int movingCount(int m, int n, int k) {
        int[][] matrix = new int[m][n];
        judge(matrix, 0, 0, k);
        return counter;
    }

    public void judge(int[][] matrix, int i, int j, int k) {
        /*
        m, n 确定范围边界
        i, j 当前坐标
        k 界限
         */
        int sum = getVal(i) + getVal(j);
        if (i < 0 || j < 0 || i > matrix.length - 1 || j > matrix[0].length - 1 || sum > k || matrix[i][j] == -1) {
            return;
        }
        counter++;
        matrix[i][j] = -1;
        judge(matrix, i + 1, j, k);
        judge(matrix, i, j + 1, k);
        judge(matrix, i - 1, j, k);
        judge(matrix, i, j + 1, k);
    }

    public int getVal(int val) {
        /*
        获取val的各位之和
         */
        int s = 0;
        while(val != 0) {
            s += val % 10;
            val = val / 10;
        }
        return s;
    }
}
